package com.ztom.daily.n2022.m4;

/**
 * 寻找比目标字母大的最小字母
 * <p>
 * https://leetcode-cn.com/problems/find-smallest-letter-greater-than-target/
 *
 * @author ZhangTao
 */
public class Day03NextGreatestLetter {

    public char nextGreatestLetter1(char[] letters, char target) {
        // 如果不存在, 返回第一个
        char res = letters[0];
        for (char letter : letters) {
            if (letter > target) {
                res = letter;
                break;
            }
        }
        return res;
    }

    public char nextGreatestLetter(char[] letters, char target) {
        // 如果不存在, 返回第一个
        char res = letters[0];

        int l = 0;
        int r = letters.length - 1;
        int mid = 0;
        while (l <= r) {
            mid = l + ((r - l) >> 1);
            if (letters[mid] > target) {
                if (mid >= 1 && letters[mid - 1] <= target) {
                    return letters[mid];
                }
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return res;
    }
}
